import java.util.ArrayList;

/**
 * Created by forcht on 2018/5/20.
 */
public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> list=new ArrayList<>();
        dfs(list,0,n,new String[n]);
        return list;
    }
    void dfs(ArrayList<String[]> list,int cur,int n,String[] s){
        if (cur>=n)list.add(s.clone());
        else {
            //判断是否会冲突
            for(int i=0;i<n;i++){
                boolean flag=false;
                for(int j=0;j<cur&&!flag;j++){
                    for(int k=0;k<n;k++){
                        if(((cur+i==(j+k)||(cur-i)==(j-k)||(i==k))&&s[j].charAt(k)=='Q')){
                            flag=true;
                            break;
                        }
                    }
                }
                if (!flag){
                    StringBuilder str=new StringBuilder();
                    for(int j=0;j<n;j++) {
                        if (j == i) str.append("Q");
                        else str.append(".");
                    }
                    s[cur]=str.toString();
                    dfs(list,cur+1,n,s);
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        ArrayList<String[]> list = solution.solveNQueens(4);
        for(int i=0;i<list.size();i++){
            String[] s=list.get(i);
            for(int j=0;j<s.length;j++){
                System.out.println(s[j]);
            }
            System.out.println("-------");
        }
    }
}
